package leetcode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 下一个更大元素 2（单调栈）
 */
public class NextGreaterElementsTwoMonotonous {
    public static int[] nextGreaterElements(int[] nums) {
        Deque<Integer> deque = new ArrayDeque<>(); // 使用栈存储数组下标
        int len = nums.length;
        int[] res = new int[len];
//        for (int i = 0; i < len; i++) {
//            res[i] = -1;
//        }
        Arrays.fill(res, -1);
        // 遍历数组nums两边才可以将所有元素的下一个更大元素找完
        for (int i = 0; i < 2 * len; i++) {
            // 若当前元素值大于栈顶元素不断弹出栈顶元素对应的值，维持栈单调递增
            while (!deque.isEmpty() && nums[deque.peek()] < nums[i % len]) {
                int index = deque.pop();
                res[index] = nums[i % len];
            }
            deque.push(i % len);
        }
        // 至此已全部找到对应的下一个最大元素
        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[] {1, 2, 1, 3, 1};
        System.out.println(Arrays.toString(nextGreaterElements(nums)));
    }
}
